//	Problem 180: Rational zeros of a function of three variables

// For any integer n, consider the three functions

// f1,n(x,y,z) = x^(n+1) + y^(n+1) − z^(n+1)
// f2,n(x,y,z) = (xy + yz + zx)*(x^(n-1) + y^(n-1) − z^(n-1))
// f3,n(x,y,z) = xyz*(x^(n-2) + y^(n-2) − z^(n-2))

// and their combination

// fn(x,y,z) = f1,n(x,y,z) + f2,n(x,y,z) − f3,n(x,y,z)

// We call (x,y,z) a golden triple of order k if x, y, and z are all rational numbers of the form a / b with
// 0 < a < b ≤ k and there is (at least) one integer n, so that fn(x,y,z) = 0.

// Let s(x,y,z) = x + y + z.
// Let t = u / v be the sum of all distinct s(x,y,z) for all golden triples (x,y,z) of order 35.
// All the s(x,y,z) and t must be in reduced form.

// Find u + v.

//-----------------------------
// fn(x,y,z)=0 ==> x^n+y^n=z^n
// For positive rational numbers n can be -2, -1, 1, or 2. ref: Fermat's last theorem.
// If n=1	==>	x+y=z
// If n=-1	==>	xy/(x+y)=z
// If n=2	==>	x^2+y^2=z^2
// If n=-2	==>	x^2*y^2/(x^2+y^2)=z^2

package main

import (
	"fmt"
	"math"
	"math/big"
	"projecteuler/euler"
	"strconv"
	"strings"
)

func p180() {
	var fs []*big.Rat = make([]*big.Rat, 0)
	for u := 1; u < 35; u++ {
		for w := u + 1; w <= 35; w++ {
			if euler.GCD(u, w) == 1 {
				fs = append(fs, big.NewRat(int64(u), int64(w)))
			}
		}
	} //383
	z1 := big.NewRat(1, 1)
	z2 := big.NewRat(1, 1)
	z3 := big.NewRat(1, 1)
	z3r := big.NewRat(1, 1)
	z4 := big.NewRat(1, 1)
	z4r := big.NewRat(1, 1)
	t1 := big.NewRat(1, 1)
	t2 := big.NewRat(1, 1)
	t3 := big.NewRat(1, 1)
	t4 := big.NewRat(1, 1)
	sum := big.NewRat(1, 1)
	var result map[string]int = make(map[string]int)
	for i := range fs {
		for j := i; j < len(fs); j++ {
			//z=x+y
			z1.Add(fs[i], fs[j])
			if s, t := z1.Denom().Int64(), z1.Num().Int64(); t < s && s <= 35 {
				sum.Add(z1, z1)
				result[sum.RatString()] = 1
			}
			//z=xy/(x+y)
			t1.Inv(z1)
			t2.Mul(fs[i], fs[j])
			z2.Mul(t1, t2)
			if s, t := z2.Denom().Int64(), z2.Num().Int64(); t < s && s <= 35 {
				sum.Add(z1, z2)
				result[sum.RatString()] = 1
			}
			//z^2=x^2+y^2
			t1.Mul(fs[i], fs[i])
			t2.Mul(fs[j], fs[j])
			z3.Add(t1, t2)
			if s, t := z3.Denom().Int64(), z3.Num().Int64(); t < s && s <= 1225 && check180(s) && check180(t) {
				z3r.SetFrac64(int64(math.Sqrt(float64(t))), int64(math.Sqrt(float64(s))))
				sum.Add(z1, z3r)
				result[sum.RatString()] = 1
			}
			//z^2=x^2*y^2/(x^2+y^2)
			t1.Mul(fs[i], fs[i])
			t2.Mul(fs[j], fs[j])
			t3.Mul(t1, t2)
			t4.Inv(z3)
			z4.Mul(t3, t4)
			if s, t := z4.Denom().Int64(), z4.Num().Int64(); t < s && s <= 1225 && check180(s) && check180(t) {
				z4r.SetFrac64(int64(math.Sqrt(float64(t))), int64(math.Sqrt(float64(s))))
				sum.Add(z1, z4r)
				result[sum.RatString()] = 1
			}
		}
	}
	ans := big.NewRat(0, 1)
	for k := range result {
		numbers := strings.Split(k, "/")
		if len(numbers) < 2 {
			i1, _ := strconv.Atoi(numbers[0])
			ans.Add(ans, big.NewRat(int64(i1), 1))
			continue
		}
		i1, _ := strconv.Atoi(numbers[0])
		i2, _ := strconv.Atoi(numbers[1])
		ans.Add(ans, big.NewRat(int64(i1), int64(i2)))
	}
	fmt.Println("Problem 180:", ans.Denom().Int64()+ans.Num().Int64())
}

func check180(s int64) bool {
	if r := int64(math.Sqrt(float64(s))); r*r == s {
		return true
	}
	return false
}
